package com.example.question.bt.backtrack2;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2023-07-17
 * @Author Jonathan
 */
public class Code06_679 {
    public static void main(String[] args) {
        Code06_679 code = new Code06_679();
//        List<String> list = new ArrayList<>();
//        code.expressions(new int[]{4, 1, 8, 7}, new char[]{'+', '-', '*', '/'}, 0, "", list);
//        System.out.println(list);
//        System.out.println(list.size());
//        List<String> parentheses = code.parentheses("4+1-8*7");
//        System.out.println(parentheses);
        System.out.println("code.judgePoint24(new int[]{5, 5, 5, 1}) = " + code.judgePoint24(new int[]{5, 5, 5, 1}));

    }

    private Double EPSILON = 1e-6;
    private Integer TARGET = 24;

    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int i = 0; i < cards.length; i++) {
            list.add((double) cards[i]);
        }
        return dfs(list);
    }

    private boolean dfs(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }

        if (list.size() == 1) {
            // 小于误差即可
            return Math.abs(list.get(0) - TARGET) < EPSILON;
        }

        int size = list.size();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j) {
                    // 取出两个数字
                    Double num1 = list.get(i);
                    Double num2 = list.get(j);
                    List<Double> childList = new ArrayList<>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) {
                            // 将除了i,j的元素放到新的数组里面
                            childList.add(list.get(k));
                        }
                    }
                    for (int k = 0; k < 4; k++) {
                        // 0 +
                        // 1 *
                        // 2 -
                        // 3 /
                        if (k < 2 && i > j) {
                            // 乘法、加法 交换律  剪枝
                            continue;
                        }
                        if (k == 0) {
                            childList.add(list.get(i) + list.get(j));
                        } else if (k == 1) {
                            childList.add(list.get(i) * list.get(j));
                        } else if (k == 2) {
                            childList.add(list.get(i) - list.get(j));
                        } else {
                            if (Math.abs(list.get(j)) < EPSILON) {
                                continue;
                            } else {
                                childList.add(list.get(i) / list.get(j));
                            }
                        }
                        if (dfs(childList)) return true;
                        childList.remove(childList.size() - 1);
                    }
                }
            }
        }
        return false;
    }

    // 拼装所有可能的表达式 还要加括号
    private void expressions(int[] cards, char[] operators, int startIndex, String expression, List<String> expressions) {
        //  最后一个数字自己手动加上
        if (startIndex == cards.length - 1) {
            expressions.add(expression + cards[cards.length - 1]);
            return;
        }

        expression += cards[startIndex];
        startIndex++;
        for (char operator : operators) {
            expressions(cards, operators, startIndex, expression + operator, expressions);
        }
    }

    // 4+1-8*7
    private List<String> parentheses(String express) {
        List<String> result = new ArrayList<>();
        StringBuilder builder = new StringBuilder();
//        String str0 = express.substring(0, 3);
//        String str1 = express.substring(3, 4);
//        String str2 = express.substring(4);
//        builder.append("(").append(str0).append(")").append(str1).append("(").append(str2).append(")");
//        String s = builder.toString();
        result.add(parentheses(express, 0, 3, 4));
        result.add(parentheses(express, 0, 5, 4));
        result.add(parentheses(express, 2, 5, 4));
        result.add(parentheses(express, 2, express.length() - 2, 4));
        return result;
    }

    private String parentheses(String str, int left, int mid, int right) {
        StringBuilder builder = new StringBuilder();
        String s = str.substring(0, left);
        String str0 = str.substring(left, mid);
        String str1 = str.substring(mid, mid + 1);
        String str2 = str.substring(mid + 1);
        builder.append(s).append("(").append(str0).append(")").append(str1);
        if (left == 0) {
            builder.append("(").append(str2).append(")");
        } else {
            builder.append(str2);
        }
        return builder.toString();
    }
}
